Uncompressed and minimally compressed formats

Why bother using someone else’s image format? It’s your data, you created it, you display it, you control it.

Advantages of doing your own format:

Less work (at least initially).

Don’t need to figure out some obscure specification and write code for unlikely situations.

You can provide for unusual requirements.

You can optimize image storage for fast display on your hardware.

You are (relatively) safe from patent and licensing issues.

Advantages of using an existing format:

You may be able to use public domain source code.

You are more likely to understand how to display this image when you (or someone else on your team) comes back to it a year later.

You do not have to write and upgrade your own display and printer drivers.

You can use image packages that let you edit your image or convert between formats.

You can easily use compression.

Shareware programs for format conversion

Key: 1: Read & write R: read W: write *: not working on CD version

Green: On CD with Miano; Blue: On CD with Murray & vanRyker

Format	xv for UNIX	Image Magick	Graphic Workshop	Graphics Viewer	Compu Pic	Vue Print	Win Jpeg	Ulead Viewer	GraphX Viewer	Paint shop pro	wcvt2 pov	Picture Man	Lview Pro	PhotoLab	FITS view	PBM plus	Totals
BMP	1	1	1	1	1	1	1	1	1	1		1	1	1	1		14
GIF	1	1	1	1	1	1	1	1	1	1		1	1	1		1	14
TGA	1	1	1	1	1	1	1	1	1	1		1	1			1	13
TIFF	1	1	1	1	R	1	1	1	1	1		1		1		1	13
JPEG	1	1	1	1	1	1	1	1	1	1		1	1				12
PCX	1	1	1	1	R	1	1	1	1	1		1				1	12
EPS	1	1						R	1	1		1				1	7
Sun Raster	1	1	1	1					1	1						1	7
FITS	1	1	1												1	1	5
Photo CD		1	*		R		1	R									5
PBM	1	1					PPM			1			1			1	6
PICT		1	1				1			1						1	5
PNG		1	1		1				1	1							5
GEM IMG			1	1												1	3
IFF/ILBM			1	1												1	3
MacPaint				1			1			1						1	4
RAW		1								1	1					1	4
WMF			*	1				R		1							4
XWD		1							1							1	3
CGM		1	*					R									3
Dr. Halo			1	1						1							3
MS ICO		1	1														2
MS Paint			1	1						1							3
PIC			1	1						1							3
WPG			1	1						1							3
3DS											1						1
DCX		1															1
	10	18	17	15	5	6	9	6	10	18	2	7	5	3	2	14

Graphic Workshop	CD version has expired. License is $40.
Graphics Viewer	CD has C and VB source code
Compu Pic
Vue Print
Win Jpeg	CD version works. If use more than 14 days, should pay $25.
Ulead Viewer
GraphX Viewer	CD version works and is free. 8 character file names.
Paint shop pro	CD version works. If use more than 30 days, pay $109 (ver 7)
wcvt2 pov
Picture Man
Lview Pro	CD version works. License is $30.
PhotoLab
FITS view
PBM plus	CD has source code designed for UNIX

For vector and game formats

MilkShape 3D www.swissquake.ch/chymbalum-soft converts among:

AutoCAD DXF

Half-life SMD

Quake MD2, MD3

AutoDesk 3DS

3Dstudio ASC

VRML1 WRL

POV-Ray INC

Unreal/UT 3D

Wavefront OBJ

RAW and others. This is shareware. You get 30 days, after which it will cost you $30 to register.

Example: a Raw Image

[ Use FRHED on Cube.raw]

Portable Bitmap Utilities

This is the simplest possible format. It was invented by Jeff Poskanzer as an intermediate format for the pbm / pbmplus image format conversion suite. There are three kinds of formats; each has an ASCII and a binary version:

Format	Magic number	Bits	For
Portable Bit Map (PBM) ASCII	P1	1	Monochrome (B&W)
Portable Gray Map (PGM) ASCII	P2	any	Gray scale
Portable Pixel Map (PPM) ASCII	P3	any	Color (RGB)
Portable Bit Map (PBM) binary	P4	1	Monochrome (B&W)
Portable Gray Map (PGM) binary	P5	1 to 8	Gray scale
Portable Pixel Map (PPM) binary	P6	1 to 24	Color (RGB)

The header is ASCII and is the same for all six formats, except that there is no MaxGray for PBM. Header entries are separated by white space.

Magic number: P1, P2, P3, P4, P5 or P6.

ImageWidth: in pixels, decimal.

ImageHeight: in pixels, decimal.

MaxGrey: Value for white or for a fully turned on color.

Use of a central format:

Direct conversion among N formats would need N (N-1) translators.

A central format requires 2 N translators.

Examples:

P1 7 6

# upper triangle is black; lower is white

# Each line of image requires 15 bytes; 90 bytes for image

0 0 0 0 0 0 1

0 0 0 0 0 1 1

0 0 0 0 1 1 1

0 0 0 1 1 1 1

0 0 1 1 1 1 1

0 1 1 1 1 1 1

# same image as above

#0 0 0 0 0 0 1 0

#0 0 0 0 1 1 0 0

#0 0 1 1 1 0 0 0

#1 1 1 1 0 0 1 1

#1 1 1 0 1 1 1 1

#1 1

# The image requires 6 bytes

7 6

0x020c38f3efc0

# A gray rectangle with a black border

# on a white background.

# Whitespace is not allowed in the pixel area

# It is given here for readability.

12 7 255

0xffff ffff ffff ffff ffff ffff

0xffff 0000 0000 0000 0000 ffff

0xffff 0080 8080 8080 8000 ffff

0xffff 0000 0000 0000 0000 ffff

0xffff ffff ffff ffff ffff ffff

Don’t use RAW images

Instead of using the raw cube image above, prefix it with the following header:

P5 64 64 255

This makes it a PGM binary image. The file size has only increased by 14 bytes for the header. We could use the Paint Shop Pro package to convert this image to bmp format and be able to display it in MS Windows.

[Demonstrate]

Magic number (hex)	Magic # (ASCII)	Format	Version	Version tag	Bits	Endian
5031	P1	PBM ASCII			1	N/A
5032	P2	PGM ASCII			any	N/A
5033	P3	PPM ASCII			any	N/A
5034	P4	PBM binary			1	N/A
5035	P5	PGM binary			1 to 8	N/A
5036	P6	PPM binary			1 to 24	N/A
89504e470d0a1a0a	\211PNG\r\n\032\n	PNG			1 to 48	Big
0000		BMP	MS Windows 1.x DDB		1, 4, 8	Little
4d42	BM	BMP	MS Windows 2.x and OS/2 1.x	12 for header size	1, 4, 8, 24	Little
4d42	BM	BMP	MS Windows 3.x	40 for header size	1, 4, 8, 24	Little
4d42	BM	BMP	MS Windows NT	40 for header size	1, 4, 8, 16, 24, 32	Little
4d42	BM	BMP	MS Windows 95	108 for header size	1, 4, 8, 16, 24, 32	Little
4d42	BM	BMP	OS/2 2.x single bitmap	typically 64 for header size	1, 4, 8, 24	Little
4142	BA	BMP	OS/2 2.x bitmap array	typically 64 for header size	1, 4, 8, 24	Little
4349	IC	BMP	OS/2 2.x icon	typically 64 for header size	1, 4, 8, 24	Little
4943	CI	BMP	OS/2 2.x color icon	typically 64 for header size	1, 4, 8, 24	Little
5450	PT	BMP	OS/2 2.x pointer	typically 64 for header size	1, 4, 8, 24	Little
5043	CP	BMP	OS/2 2.x color pointer	typically 64 for header size	1, 4, 8, 24	Little
0a		PCX		In 2nd byte	1, 2, 4, 8	Little
3ade68b1		DCX	PCX for fax		typically 1	Little
ffd8ffe0xxxx4a46494600	…JFIF	JPEG JFIF		In bytes 10 and 11	1 to 8 [or 12] per component	Big
474946	GIF	GIF	"87a" or "89a"	In bytes 4-6	1 to 8	Little
	none	Dr. Halo CUT			1 to 8	Little
4148	AH	Dr. Halo PAL		In bytes 3 and 4	1 to 8	Little
	none	TGA		v2.0 signature in footer	8, 16, 24, 32	Little
49492a00	II\2a	TIFF			1 to 24	Little
4d4d002a	MM\2a	TIFF			1 to 24	Big
ab01		VIFF		In byte 4	any	any
ff575043		WPG			8	Big
4245474d46	BEGMF	CGM	clear text encoding		any	N/A
38425053	8BPS	PSD Adobe Photoshop			any	Big
512 byte	Macintosh header	PICT			1 to 24	Big

Design case

QC-10 image requirements

At each point scanned, there is:

Image Compression

Why do we want to compress images?

A 1000 x 1000 image with 24 bit color takes 3 MB.

A 4000 x 4000 24 bit color image takes 48 MB.

These hog RAM and disk space and take forever to download on a web page.

It gets worse for digital video:

Video Format	Pels x lines x frames/s	Uncompressed Mbits / s	MPEG bitrate (Mbits / s)
NTSC	480 x 480 x 30	168	4 to 8
PAL [Europe]	576 x 576 x 25	199	4 to 9
HDTV	1920 x 1080 x 30	1493	18 to 30
HDTV	1280x 720 x 60	1327	18 to 30

These uncompressed bitrates will not only overwhelm your dial-up modem, but other media as well:

Medium	Bit rate (Mbits/s)
ISDN	0.064 to 1.920
CD-ROM (normal speed)	1.4
LAN	10 to 100
DVD	9 to 10
Broadcast video	18 to 20
CATV	20 to 40

Analog TV (NTSC) has a bandwidth of 6 MHz. This can carry a compressed HDTV signal or four to ten compressed lower definition audio-visual channels.

At 4 Mbits/s, a full length movie can fit on a DVD.

Disadvantages of image compression

It takes longer to display the image.

Software is more complicated.

The person viewing the image must have the right software.

Some methods are proprietary or patented.

Terminology

Image compression can be symmetric (same amount of work to compress and decompress) or asymmetric. JPEG and MPEG are asymmetric; it takes more time to encode an image than decode it. MPEG encoding requires special hardware.

Lossless compression means that after you compress and decompress an image, you have exactly what you started out with, bit for bit. Lossy compression gives you something that is not identical to what you started with. An image compressed with a good lossy technique may be visually indistinguishable from the original. Higher compression ratios can be achieved with lossy methods.

Measure of performance:

Compression ratio: Number of bits before compression / Bits after compression.

Rate: Average number of bits for one sample.

Distortion: Difference between original and reconstructed data.

Low distortion means high quality or high fidelity.

Modeling and Coding

The first phase of data compression is modeling: describe the redundancy in the data.

The second phase is coding.

The residual is the difference between the model and the data.

Example 1.2.1 from Sayood:

Data	9	11	11	11	14	13	15	17	16	17	20	21
Model	9	10	11	12	13	14	15	16	17	18	19	20
Residual	0	1	0	-1	1	-1	1	0	1	-1	1	1

It would take 5 bits to transmit the original data series. If we model it as x_n = n + 8, then we can transmit the residual using only 2 bits per sample and get 2.5:1 lossless compression.

Example 1.2.2 from Sayood:

Data	27	28	29	28	26	27	29	28	30	32	34	36	38
Difference	27	1	1	-1	-2	1	2	-1	2	2	2	2	2

This is predictive coding, in which each value is predicted from the previous value(s). Here the prediction is that it will be the same. We need to transmit the first value, but the differences can be sent using fewer bits.

Example 1.2.2 from Sayood:

Given a typical text with 8 symbols:

a_barayaran_array_ran_far_faar_faaar_away

This could be done with 3 bits for each symbol.

Using variable length codewords, we could represent

a	1
_	001
b	01100
f	0100
n	0111
r	000
w	01101
y	0101

This winds up using 106 bits for the 41 symbols instead of 123 for 1.16:1 compression.

Homework:

See these files for assignments due:

1/14/04 Week1

1/21//04 Week2

1/28/04 Week3

The proper naming convention must be used.

Run Length Encoding

If we look at the simple images that we have considered so, far we can come up with an easy way to compress them. For example:

# A gray rectangle with a black border

# on a white background.

# Whitespace is not allowed in the pixel area

# It is given here for readability.

12 7 255

0xffff ffff ffff ffff ffff ffff

0xffff 0000 0000 0000 0000 ffff

0xffff 0080 8080 8080 8000 ffff

0xffff 0000 0000 0000 0000 ffff

0xffff ffff ffff ffff ffff ffff

The first line has 12 ff’s so we can write it as 12 ff.

We could do the second line as 2 ff, 8 00, 2 ff and the other lines as

2 ff, 1 00, 6 80, 1 00, 2 ff

2 ff, 8 00, 2 ff

12 ff

This is Run Length Encoding (RLE).

If we use one byte for the run count and one for the run value, we can represent this image in 46 bytes instead of the original 84. This is 55% of the original size, so we have a compression ration of nearly 2:1

RLE tends to work better in graphics than in photos.

[Miano figures 1-7 thru 1-10]

BMP Format

You are unlikely to encounter anything older than Windows version 3.

There is a variant for OS/2.

BMP files can be compressed using RLE, but this is unusual.

File Header

Bitmap Header

Color Palette

Bitmap Data

File Header

typedef struct _WinBMPFileHeader

{

WORD FileType; /* 0x00: File type, always 4D42h ("BM") */

DWORD FileSize; /* 0x02: Size of the file in bytes

Usually 0 in uncompressed images */

WORD Reserved1; /* Always 0 */

WORD Reserved2; /* Always 0 */

DWORD BitmapOffset; /* 0x0A: Starting position of image data in bytes */

} WINBMPFILEHEADER;

Bitmap Header

typedef struct _WinBitmapHeader

{

DWORD Size; /* 0x0E: Size of this header in bytes

12 for OS/2

40 for Windows 3.x and NT

108 for Windows 95 [BmpVersion4] */

LONG Width; /* 0x12: Image width in pixels */

LONG Height; /* 0x16: Image height in pixels

If Height is a positive number, then the image is a

"bottom-up" bitmap with the origin in the lower-left corner.

If Height is a negative number, then the image is a

"top-down" bitmap with the origin in the upper-left corner. */

WORD Planes; /* 0x1A: Number of color planes; always 1 */

WORD BitsPerPixel; /* 0x1C: Number of bits per pixel

1, 4, 8, and 24 are the only legal values for Windows 3.x / NT.

For Windows 95: 1, 4, 8, 16, 24, 32. */

/* Fields added for Windows 3.x follow this line */

DWORD Compression; /* 0x1E: Compression methods used

0 indicates that the data is uncompressed;

1 indicates that the 8-bit RLE algorithm was used;

2 indicates that the 4-bit RLE algorithm was used

3 [not for Windows 3.x] bitsfield encoding. Must be used when BitsPerPixel = 16 or 32 */

DWORD SizeOfBitmap; /* 0x22: Size of bitmap in bytes

Typically 0 when uncompressed */

LONG HorzResolution; /* 0x26: Horizontal resolution in pixels per meter */

LONG VertResolution; /* 0x2A: Vertical resolution in pixels per meter */

DWORD ColorsUsed; /* 0x2E: Number of colors in the image */

DWORD ColorsImportant; /* 0x32: Minimum number of important colors */

#ifdef BmpVersion4

/* Fields added for Windows 4.x follow this line */

DWORD RedMask; /* 0x36: Mask identifying bits of red component */

DWORD GreenMask; /* Mask identifying bits of green component */

DWORD BlueMask; /* Mask identifying bits of blue component */

DWORD AlphaMask; /* Mask identifying bits of alpha component */

DWORD CSType; /* Color space type

0 calibrated RGB; next 12 values define CIE colors.

1 device-dependent RGB

2 device-dependent CMYK */

LONG RedX; /* X coordinate of red endpoint */

LONG RedY; /* Y coordinate of red endpoint */

LONG RedZ; /* Z coordinate of red endpoint */

LONG GreenX; /* X coordinate of green endpoint */

LONG GreenY; /* Y coordinate of green endpoint */

LONG GreenZ; /* Z coordinate of green endpoint */

LONG BlueX; /* X coordinate of blue endpoint */

LONG BlueY; /* Y coordinate of blue endpoint */

LONG BlueZ; /* Z coordinate of blue endpoint */

DWORD GammaRed; /* Gamma red coordinate scale value */

DWORD GammaGreen; /* Gamma green coordinate scale value */

DWORD GammaBlue; /* Gamma blue coordinate scale value */

#endif /* BmpVersion4 */

} WINBITMAPHEADER;

Color Palette

For Windows 3.x or NT (compression != 3) :

typedef struct _Win3xPaletteElement

{ /* palette starts at 0x36 and ends at 0x75 */

BYTE Blue; /* Blue component */

BYTE Green; /* Green component */

BYTE Red; /* Red component */

BYTE Reserved; /* Padding (always 0) */

} WIN3XPALETTEELEMENT;

For Windows NT (compression == 3):

typedef _WinNtBitfieldsMasks

{

DWORD RedMask; /* Mask identifying bits of red component */

DWORD GreenMask; /* Mask identifying bits of green component */

DWORD BlueMask; /* Mask identifying bits of blue component */

} WINNTBITFIELDSMASKS;

For 16 bits, typically use:

RedMask = 0xF8000000;

GreenMask = 0x07E00000;

BlueMask = 0x001F0000;

For 32-bit bitmaps, typically:

RedMask = 0xFFC00000;

GreenMask = 0x003FF000;

BlueMask = 0x00000FFC;

Bitmap Data

Example: EditCut.bmp

Open EditCut.bmp with MS Paint. Image | Attributes shows 26 x 24.

Open EditCut.bmp with Witched. We see:

FileType: 42 4D // Windows BMP

FileSize: F6 01 00 00 // 0x1F6 = 502

BitmapOffset: 76 00 00 00

Size: 28 00 00 00 // 40 bytes for Windows 3.x or NT

Width: 1A 00 00 00 // 26

Height: 18 00 00 00 // 24

Planes: 01 00

BitsPerPixel: 04 00

Compression: 00 00 00 00

SizeOfBitmap: 80 01 00 00 // 384 bytes = 16 * 24

The palette is:

Blue	Green	Red	Fill	Index	Color
00	00	00	00	0	Black
00	00	80	00	1	Dark Red
00	80	00	00	2	Dark Green
00	80	80	00	3	Brown
80	00	00	00	4	Dark Blue
80	00	80	00	5	Dark Magenta
80	80	00	00	6	Dark Cyan
80	80	80	00	7	Gray
c0	c0	c0	00	8	Light Gray
00	00	ff	00	9	Red
00	ff	00	00	A	Green
00	ff	ff	00	B	Yellow
ff	00	00	00	C	Blue
ff	00	ff	00	D	Magenta
ff	ff	00	00	E	Cyan
ff	ff	ff	00	F	White

The bitmap data starts at 0x76. Each nibble is an index to the palette. We can see that the indices used are: 0, 4, 7, 8, and F. The 4s for dark blue are for the scissors handles. They occur in the first half of the bitmap data, confirming that the image is scanned from bottom-up. The first 13 bytes of the image are 0xFF, representing a row of 26 white pixels.

If all 24 rows used 13 bytes, the SizeOfBitmap would be 24 * 13 = 312. But it is 384, so each row must be 16 bytes. There are 6 nibbles of fill at the end of each row.

If we display the image with 16 bytes across, we can see the pattern. The scissors handles are 4s and the blades are 0s.

Exercise: Make the corners red

BMP RLE

If you always use a RLE packet consisting of a (run count, run value), you can get into trouble if there are no runs in the image. You would replace each pixel value by (1, value) and your image would be twice as large!

Thus for practical RLE, we need an escape code to tell us not to use runs.

The MS Windows Bitmap format uses the following markers:

00 xx: Unencoded run of xx bytes. 3 £ xx £ 255

00 00: End-of-scan-line.

00 01: End-of-RLE-data.

00 02 xx yy: delta code

[Example: Winter.bmp]

The first line of data is:

00 05 37 73 37 01 // unencoded run of 5 pixels: 3, 7, 7, 3, 3

The last 7 is ignored and the 01 is a fill character to make an even number of bytes.

08 77 // 8 gray pixels

02 33 // 2 brown

11 77 // 17 gray

00 00 // end of scan line

More on RLE

It is possible to do lossy RLE, where you drop the low order bits to get longer runs.

Should code one line at a time to reduce the buffer space needed.

This helps you avoid cross-coding (merging two scan lines).

When scan lines are merged, decoding is more complicated.

Cross-coded images may display on one application but not on another.

A format may want to include a scan-line table to make it easier to display part of an image.

Vertical replication packet: Can use a special value (e.g. a run of length 0) to show that a whole line is repeated.

More on BMP

Can we make the scissors handle red by editing the palette?

[Look at ImageMagick.bmp]

Cover formats for 16, 24, 32 bit images and Version 4

Spelling

Palette is used by an artist.

Pallet is used by a forklift.

Pallette is an armpit plate on a suit of armor.

Palet is a botanical term.

Next Lecture

Syllabus

Homework